//============================================================================
// Name        : Struktury.cpp
// Author      : Hanna Sienkiewicz 184184
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdlib>
#include <string.h>
#include <fstream>
#include "Kolejka.h"
#include "Lista.h"
#include "Stos.h"
#include "Kopiec.hh"
#include "BST.h"
#include "AVL.h"
#include "red_black_tree.h"


using namespace std;

	Kolejka* kolejka=new Kolejka();
	Lista* lista=new Lista();
	Stos* stos=new Stos();
	Kopiec* kopiec=new Kopiec();
	bst* binarne=new bst();
	AVL* avl=new AVL();
	rb_red_blk_tree* tree;


typedef unsigned long long timestamp; // zmiena przechowujaca czas;

void IntDest(void* a) {
  free((int*)a);
}



int IntComp(const void* a,const void* b) {
  if( *(int*)a > *(int*)b) return(1);
  if( *(int*)a < *(int*)b) return(-1);
  return(0);
}

void IntPrint(const void* a) {
  printf("%i",*(int*)a);
}

void InfoPrint(void* a) {
  ;
}

void InfoDest(void *a){
  ;
}
		// funkcja do mierzenia czasu
static timestamp gettimestamp(){
	struct timeval now;
	gettimeofday(&now,NULL);
	return now.tv_usec+(timestamp)now.tv_sec*1000000;
}

double sprawdzKolejkaDodawanie(int* tab, int size){
	kolejka->wyczysc();
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		kolejka->Dodaj_element(tab[i]);
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzKolejkaUsuwanie(int* tab, int size){
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		kolejka->Usun_pierwszy_element();
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzListaDodawanie(int* tab, int size){
	lista->wyczysc();
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		lista->Dodaj_element(tab[i]);
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzListaUsuwanie(int* tab, int size){
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		lista->Usun_pierwszy_element();
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzRBDodawanie(int* tab, int size){
	tree=RBTreeCreate(IntComp,IntDest,InfoDest,IntPrint,InfoPrint);
	 int newKey,newKey2;
	 int* newInt;
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		newInt=(int*) malloc(sizeof(int));
		*newInt=newKey;
		RBTreeInsert(tree,newInt,0);
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzRBUsuwanie(int* tab, int size){
	timestamp t0=gettimestamp();
	void* newKey;
    rb_red_blk_node* newNode;
	for(int i=0;i<size;i++){
		  newKey=(tree->root->key);
		  if ( ( newNode=RBExactQuery(tree,newKey ) ) )
			  RBDelete(tree,newNode);/*assignment*/
		  else
			  printf("key not found in tree, no action taken\n");}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzStosDodawanie(int* tab, int size){
	stos->wyczysc();
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		stos->Dodaj_element(tab[i]);
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzStosUsuwanie(int* tab, int size){
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		stos->Usun_pierwszy_element();
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzKopiecDodawanie(int* tab, int size){
	kopiec->heap();
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		kopiec->insert(tab[i]);
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzKopiecUsuwanie(int* tab, int size){
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		kopiec->deletemax();
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzBSTDodawanie(int* tab, int size){
	binarne->wyczysc();
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		binarne->dodaj(tab[i]);
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzBSTUsuwanie(int* tab, int size){
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		binarne->usun(binarne->root());
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzAVLDodawanie(int* tab, int size){
	avl->clear();
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		avl->insert(tab[i]);
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

double sprawdzAVLUsuwanie(int* tab, int size){
	timestamp t0=gettimestamp();
	for(int i=0;i<size;i++){
		avl->extract(avl->root->data);
	}
	timestamp t1=gettimestamp();
	return (t1-t0)/1000000.0L;
}

//double* sprawdzwydajnoscUsuwanie(int n){
//	cout << "\n\nUsuwanie losowych elementow: " << n << "\n";
//	double* w=new double[6];
//	int* tab=new int[n];
//	int* tabpom=NULL;
//	srand(time(0));
//	for(int i=0;i<n;i++){
//		tab[i]=rand()%n;
//	}
//	w[0]=n; // ilosc elementow do dodania
//
//
//	for(int i=0;i<1;i++){
//		tabpom=new int[n];
//		memcpy(tabpom,tab,n);
//		w[1]+=sprawdzBSTUsuwanie(tabpom,n);
//		delete tabpom;
//	}
//	//w[1]/=10;
//	cout << "BST: " << w[1] << " sek\n";
//}


void sprawdzwydajnosc(int n, double** addTab, double** deleteTab, int index ){
	cout << "\n\nUsuwanie losowych elementow: " << n << "\n";
	double* w=new double[7];
	double* d=new double[7];
	int* tab=new int[n];
	int* tabpom=NULL;
	srand(time(0));
	for(int i=0;i<n;i++){
		tab[i]=rand()%n;
	}
	w[0]=n; // ilosc elementow do dodania
	d[0]=n;
//	// Dodawanie do kolejki
//	for(int i=0;i<1;i++){
//		tabpom=new int[n];
//		memcpy(tabpom,tab,sizeof(int)*n);
//		w[1]+=sprawdzKolejkaDodawanie(tabpom,n);
//		delete tabpom;
//	}
//	// Usuwanie z kolejki
//	for(int i=0;i<1;i++){
//			tabpom=new int[n];
//			memcpy(tabpom,tab,sizeof(int)*n);
//			d[1]+=sprawdzKolejkaUsuwanie(tabpom,n);
//			delete tabpom;
//		}
//	//w[1]/=10;
//	cout << "Kolejka dodawanie: " << w[1] << " sek\n";
//	cout << "Kolejka usuwanie: " << d[1] << " sek\n";
//
//	// Dodawanie do kopca
//	for(int i=0;i<1;i++){
//		tabpom=new int[n];
//		memcpy(tabpom,tab,sizeof(int)*n);
//		w[2]+=sprawdzKopiecDodawanie(tabpom,n);
//		delete tabpom;
//	}
//	// Usuwanie z kolejki
//	for(int i=0;i<1;i++){
//			tabpom=new int[n];
//			memcpy(tabpom,tab,sizeof(int)*n);
//			d[2]+=sprawdzKopiecUsuwanie(tabpom,n);
//			delete tabpom;
//		}
//	//w[1]/=10;
//	cout << "Kopiec dodawanie: " << w[2] << " sek\n";
//	cout << "Kopiec usuwanie: " << d[2] << " sek\n";

	// Dodawanie do DRZEWA R&B
	for(int i=0;i<1;i++){
		tabpom=new int[n];
		memcpy(tabpom,tab,sizeof(int)*n);
		w[3]+=sprawdzRBDodawanie(tabpom,n);
		delete tabpom;
	}
	// Usuwanie z DRZEWA R&B
	for(int i=0;i<1;i++){
			tabpom=new int[n];
			memcpy(tabpom,tab,sizeof(int)*n);
			d[3]+=sprawdzRBUsuwanie(tabpom,n);
			delete tabpom;
		}
	//w[1]/=10;
	cout << "drzewo RB: " << w[3] << " sek\n";
	cout << "drzewo RB: " << d[3] << " sek\n";


//	// Dodawanie do listy
//	for(int i=0;i<1;i++){
//		tabpom=new int[n];
//		memcpy(tabpom,tab,sizeof(int)*n);
//		w[3]+=sprawdzListaDodawanie(tabpom,n);
//		delete tabpom;
//	}
//	// Usuwanie z Listy
//	for(int i=0;i<1;i++){
//			tabpom=new int[n];
//			memcpy(tabpom,tab,sizeof(int)*n);
//			d[3]+=sprawdzListaUsuwanie(tabpom,n);
//			delete tabpom;
//		}
//	//w[1]/=10;
//	cout << "Lista dodawanie: " << w[3] << " sek\n";
//	cout << "Lista usuwanie: " << d[3] << " sek\n";

//	// Dodawanie do stosu
//		delete tabpom;
//	for(int i=0;i<1;i++){
//		tabpom=new int[n];
//		memcpy(tabpom,tab,sizeof(int)*n);
//		w[4]+=sprawdzStosDodawanie(tabpom,n);
//	}
//	// Usuwanie z stos
//	for(int i=0;i<1;i++){
//			tabpom=new int[n];
//			memcpy(tabpom,tab,sizeof(int)*n);
//			d[4]+=sprawdzStosUsuwanie(tabpom,n);
//			delete tabpom;
//		}
//	//w[1]/=10;
//	cout << "Stos dodawanie: " << w[4] << " sek\n";
//	cout << "Stos usuwanie: " << d[4] << " sek\n";
//
//	// Dodawanie do BST
//	for(int i=0;i<1;i++){
//		tabpom=new int[n];
//		memcpy(tabpom,tab,sizeof(int)*n);
//		w[5]+=sprawdzBSTDodawanie(tabpom,n);
//		delete tabpom;
//	}
//	// Usuwanie z BST
//	for(int i=0;i<1;i++){
//			tabpom=new int[n];
//			memcpy(tabpom,tab,sizeof(int)*n);
//			d[5]+=sprawdzBSTUsuwanie(tabpom,n);
//			delete tabpom;
//		}
//	//w[1]/=10;
//	cout << "BST dodawanie: " << w[5] << " sek\n";
//	cout << "BST usuwanie: " << d[5] << " sek\n";
//
//	// Dodawanie do AVL
//	for(int i=0;i<1;i++){
//		tabpom=new int[n];
//		memcpy(tabpom,tab,sizeof(int)*n);
//		w[6]+=sprawdzAVLDodawanie(tabpom,n);
//		delete tabpom;
//	}
//	// Usuwanie z AVL
//	for(int i=0;i<1;i++){
//			tabpom=new int[n];
//			memcpy(tabpom,tab,sizeof(int)*n);
//			d[6]+=sprawdzAVLUsuwanie(tabpom,n);
//			delete tabpom;
//		}
//	//w[1]/=10;
//	cout << "AVL dodawanie: " << w[6] << " sek\n";
//	cout << "AVL usuwanie: " << d[6] << " sek\n";
//
	addTab[index]=w;
	deleteTab[index]=d;

//	// Dodawanie do listy
//	for(int i=0;i<1;i++){
//		tabpom=new int[n];
//		memcpy(tabpom,tab,n);
//		w[2]+=sprawdzListaDodawanie(tabpom,n);
//		delete tabpom;
//	}
//	//w[2]/=1;
//	cout << "Lista: " << w[2] << " sek\n";
//
////	// Dodawanie do stosu
//		memcpy(tabpom,tab,n);
//	for(int i=0;i<1;i++){
//		tabpom=new int[n];
//		w[3]+=sprawdzStosDodawanie(tabpom,n);
//		delete tabpom;
//	}
//	w[3]/=10;
//	cout << "Stos: " << w[3] << " sek\n";
//
//	// Dodawanie do kopca
//	for(int i=0;i<1;i++){
//		tabpom=new int[n];
//		memcpy(tabpom,tab,n);
//		w[4]+=sprawdzKopiecDodawanie(tabpom,n);
//		delete tabpom;
//	}
//	//w[4]/=10;
//	cout << "Kopiec: " << w[4] << " sek\n";
//
//	// Dodawanie do BST
//	for(int i=0;i<1;i++){
//		tabpom=new int[n];
//		memcpy(tabpom,tab,n);
//		w[5]+=sprawdzBSTDodawanie(tabpom,n);
//		delete tabpom;
//	}
//	//w[4]/=10;
//	cout << "BST: " << w[5] << " sek\n";
//
//	return w;
}

void zapiszNazwe(double** w, int size,int kolumna, string name){
	fstream plik( name.c_str(), ios::out );
		    if( plik.good() )
		    {
		        for( int i = 0; i < size; i++ )
		        {
		            plik << w[i][kolumna] << "\n";
		            plik.flush();
		        }
		        plik.close();
		    }
}

void zapisz(double** wyniki,int size,string napis){
	zapiszNazwe(wyniki,size,0,"Struktury_Ilosc_elementow.txt");
//	zapiszNazwe(wyniki,size,1,"Kolejka_"+napis+".txt");
//	zapiszNazwe(wyniki,size,2,"Kopiec_"+napis+".txt");
	zapiszNazwe(wyniki,size,3,"RB_"+napis+".txt");
//	zapiszNazwe(wyniki,size,4,"Stos_"+napis+".txt");
//	zapiszNazwe(wyniki,size,5,"BST_"+napis+".txt");
//	zapiszNazwe(wyniki,size,6,"AVL_"+napis+".txt");
}




int main() {
	int liczb_prob=20;
	int* axis=new int[liczb_prob];

	for(int i=1;i<=liczb_prob;i++){
		axis[i-1]=i*5000;
	}

	double** wynikiAdd=new double*[liczb_prob];
	double** wynikiDelete=new double*[liczb_prob];
//	wyniki[0]=sprawdzwydajnoscUsuwanie(100);
	for(int i=0;i<liczb_prob;i++){
		sprawdzwydajnosc(axis[i],wynikiAdd,wynikiDelete,i);
	}

	cout << "\n\nDodawanie elementow: \n";
	for(int i=0;i<liczb_prob;i++){
//		for(int j=0;j<5;j++){
			cout << wynikiAdd[i][3] << ", ";
//		}
		cout << endl;
	}

	zapisz(wynikiAdd,liczb_prob,"dodawanieEL");
	zapisz(wynikiDelete,liczb_prob,"UsuwanieEL");
	return 0;
}
